package io.github.hadyang.leetcode.offer;

import java.util.LinkedList;

import io.github.hadyang.leetcode.TreeNode;

/** @author haoyang.shi */
public class SerializeTree {

  String Serialize(TreeNode root) {
    if (root == null) return "";

    LinkedList<String> res = new LinkedList<>();

    serialize(res, root);

    StringBuilder builder = new StringBuilder();
    res.forEach(v -> builder.append(v).append(","));

    return builder.toString();
  }

  private void serialize(LinkedList<String> res, TreeNode root) {
    if (root == null) {
      res.addLast("$");
      return;
    }

    res.addLast(String.valueOf(root.val));
    serialize(res, root.left);
    serialize(res, root.right);
  }

  TreeNode Deserialize(String str) {
    if (str == null || str.length() == 0) return null;

    return deserialize(str.split(","), new int[] {0});
  }

  private TreeNode deserialize(String[] str, int[] index) {
    if (index[0] >= str.length) return null;

    String c = str[index[0]++];
    if (c.equals("$")) return null;

    TreeNode node = new TreeNode(Integer.valueOf(c));
    node.left = deserialize(str, index);
    node.right = deserialize(str, index);

    return node;
  }
}
